package com.cwj.algorithm.graph;

import com.cwj.algorithm.priority.IndexPriorityQueue;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 最短路径树
 * @author chenwujie
 * @date 2020-12-25 16:22
 */
public class DjikstraSP {
    /**
     * 加权有向图
     */
    private EdgeWeightedDigraph edgeWeightedDigraph;
    /**
     * 起点
     */
    private final int start;
    /**
     * 起点到该顶点的最短路径上的最后一条边
     */
    private DirectedEdge[] edgeTo;
    /**
     * 起点到该顶点(下标)最短路径总权重
     */
    private int[] distTo;

    /**
     * 最小索引优先队列维护 横切边权重
     */
    private IndexPriorityQueue<Integer> pq;

    public DjikstraSP(EdgeWeightedDigraph edgeWeightedDigraph, int start){
        this.edgeWeightedDigraph = edgeWeightedDigraph;
        this.start = start;
        this.edgeTo = new DirectedEdge[edgeWeightedDigraph.getV()];
        this.distTo = new int[edgeWeightedDigraph.getV()];
        Arrays.fill(distTo, Integer.MAX_VALUE);
        this.pq = new IndexPriorityQueue<>(edgeWeightedDigraph.getE(), true);
    }

    /**
     * 松弛顶点v
     * @param v
     */
    private void relax(int v){
        Deque<DirectedEdge> directedEdges = edgeWeightedDigraph.edgesByV(v);
        for (DirectedEdge edge : directedEdges) {
            int w = edge.getTo();

            if(distTo[v] + edge.getWeight() < distTo[w]){
                distTo[w] = distTo[v] + edge.getWeight();
                edgeTo[w] = edge;

                if(pq.contains(w)){
                    pq.change(w, distTo[w]);
                }else{
                    pq.insert(w, distTo[w]);
                }
            }
        }
    }

    /**
     * 生成最短路径树
     */
    public void sp(){
        distTo[start] = 0;
        pq.insert(start, 0);
        while(!pq.isEmpty()){
            relax(pq.removeFirst());
        }
    }

    /**
     * 获取从起点到顶点v的总权重
     * @param v
     * @return
     */
    public int getWeightTotalByV(int v){
        return distTo[v];
    }

    /**
     * 从起点到顶点v是否可达
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return distTo[v] != Integer.MAX_VALUE;
    }

    /**
     * 获取从起点到顶点v的最短路径
     * @param v
     * @return
     */
    public Deque<DirectedEdge> pathTo(int v){
        if(hasPathTo(v)){
            Deque<DirectedEdge> edges = new LinkedList<>();
            while(true){
                DirectedEdge directedEdge = edgeTo[v];
                if(directedEdge == null){
                    break;
                }
                edges.push(directedEdge);
                v = directedEdge.getFrom();
            }
            return edges;
        }else{
            return null;
        }
    }

}
